#include <vector>

namespace Geometry
  {
  enum EBoundingDirection
    {
    BD_VERTICAL,
    BD_HORIZONTAL
    };

  typedef struct {double x; double y;} TPoint2d;
  
  class KdTree2dNode
    {
    public:
      KdTree2dNode(EBoundingDirection i_direction, double i_coord, const TPoint2d* ip_point, KdTree2dNode* ip_left, KdTree2dNode* ip_right);

      EBoundingDirection GetDirection() const;
      double GetCoord() const;

    private:
      EBoundingDirection m_direction;
      double m_coord;

      const KdTree2dNode* mp_left;
      const KdTree2dNode* mp_right;

      const TPoint2d* mp_point;
    };

  class KdTree2d
    {
    public:
      KdTree2d(const std::vector<TPoint2d>& i_points);

      TPoint2d GetNearestPoint() const;
    private:

      KdTree2dNode* mp_root;
      
      KdTree2dNode* _Construct(const std::vector<TPoint2d>& i_points, EBoundingDirection i_direction);

    };


  }